package com.dmall.graph.shortest.path;

import com.dmall.graph.WeightedGraph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 迪杰斯特拉算法
 * 求単源最短路径
 * @author: xiao1.wang
 * @date: 2022/8/29 23:24
 */
public class Dijkstra {

    private WeightedGraph G;
    private int s;
    private boolean[] visited;
    private int[] dis;
    private int[] pre;

    public Dijkstra(WeightedGraph G, int s) {
        this.G = G;
        G.validateVertex(s);
        this.s = s;

        this.visited = new boolean[G.V()];
        this.dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        this.pre = new int[G.V()];
        Arrays.fill(pre, -1);

        dis[s] = 0;
        pre[s] = s;

        while (true) {
            int min = -1;
            int minDis = Integer.MAX_VALUE;
            for (int v = 0; v < G.V(); v++) {
                if (!visited[v] && dis[v] < minDis) {
                    min = v;
                    minDis = dis[v];
                }
            }
            if (min == -1) {
                break;
            }
            visited[min] = true;
            for (int w : G.adj(min)) {
                if (!visited[w] && G.getWeight(min, w) + minDis < dis[w]) {
                    dis[w] = G.getWeight(min, w) + minDis;
                    pre[w] = min;
                }
            }
        }
    }

    public boolean isConnectedTo(int t) {
        G.validateVertex(t);
        return visited[t];
    }

    public int distTo(int t) {
        if (isConnectedTo(t)) {
            return dis[t];
        }
        throw new IllegalArgumentException(String.format("No edge %d-%d", s, t));
    }

    public Iterable<Integer> path(int t) {
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        String filename = Dijkstra.class.getClassLoader().getResource("wg.txt").getPath();
        WeightedGraph g = new WeightedGraph(filename);
        Dijkstra dijkstra = new Dijkstra(g, 0);
        for (int v = 0; v < g.V(); v++) {
            System.out.println(dijkstra.s + " -> " + v + ": " + dijkstra.distTo(v) + ", path = " + dijkstra.path(v));
        }
        System.out.println();
    }
}
